المقدِّمة
تُعَدُّ هياكل البيانات ذات الدور المحوري في تصميم الخوارزميات وتطوير البرمجيّات ذات الأداء المرتفع. في بيئة جافا، تُعَدُّ فئة java.util.TreeMap واحدة من أبرز الهياكل القياسيّة التي تُطبِّق خريطة مرتَّبة (Ordered Map) من خلال شجرة بحث ثنائية متوازنة من النوع Red‑Black Tree. يهدف هذا المقال المطوَّل إلى توضيح الجوانب النظريّة والعمليّة لتحليل زمن تشغيل العمليات الأساسيّة في TreeMap، مع ربطها بمفاهيم نظرية التعقيد الحسابي وخصائص الشجرة الحمراء‑السوداء التي يستند إليها التنفيذ. كما نتناول تفصيلاً أثر العوامل الداخليّة (كآلية الموازنة) والخارجيّة (كحجم البيانات، أنماط الوصول، خصائص العتاد الافتراضي) على الأداء، مدعومين بأمثلة توضيحيّة ومقارنات رقمية ومناقشات معمَّقة حول أفضل الممارسات في استخدام TreeMap ضمن مشاريع برمجيّة حقيقية.
1. لمحة معمَّقة عن TreeMap وشجيرات Red‑Black Tree
1.1 المفهوم البنيوي للخريطة المرتَّبة
-
TreeMap تُخزِّن أزواج المفتاح/القيمة مرتَّبةً وفق ترتيب طبيعي (Comparable) أو مُحدَّد مُسبقاً (Comparator). -
-
تعتمد على شجرة Red‑Black، وهي شجرة بحث ثنائية ذات شروط تلوين صارمة تضمن الارتفاع اللوغاريتمي.
1.2 خصائص التوازن
-
الشرط الأساسي: لا يُسمح بوجود مسار أطول من الضعف لمسار آخر من الجذر لأيّ عقدة طرفية.
-
النتيجة: حدٌّ علوي للارتفاع =
2 * log2(n+1) تقريباً، ما يضمن حدوداً زمنية لوغاريتمية لعمليات الإدراج، الحذف، والبحث.
2. تحليل التعقيد الزمني النظري
| العملية | التعقيد في أسوأ حالة | التعقيد في أفضل حالة | التعقيد في الحالة المتوقَّعة |
|---|---|---|---|
put(K,V) |
O(log n) |
O(1) حين n=1 |
O(log n) |
get(Object key) |
O(log n) |
O(1) للعقدة الجذرية |
O(log n) |
remove(Object key) |
O(log n) |
O(1) لشجرة من عُقدتين |
O(log n) |
firstKey()، lastKey() |
O(log n) (عملياً O(1) بالوصول للجذر أو أقصى اليسار/اليمين) |
O(1) |
O(1) |
عمليات الرؤية الفرعيّة subMap, headMap, tailMap |
O(log n) للتهيئة + O(k) للتكرار |
O(k) إذا بدأت من الجذر |
O(log n + k) |
ملاحظة:
k يرمز لعدد العناصر المُسترجَعة في العمليات المُجزَّأة.
3. مراحل التنفيذ الداخلي لعمليات TreeMap
3.1 إدراج عنصر put
-
مسار بحث لوغاريتمي عن موضع المفتاح.
-
إنشاء عقدة جديدة؛ ربطها وفق ترتيب الترتيب.
-
ضبط الألوان وإعادة التوازن عبر الدورانات (Rotate Left/Right).
-
تحديث مُتغيِّر الحجم وبعض المؤشرات (الأصغر/الأكبر).
3.2 استرجاع get
-
مسار مقارنة مفاتيح من الجذر نزولاً حتى العثور على تطابق أو وصول عقدة فارغة.
3.3 حذف remove
-
العثور على العقدة الهدف.
-
إن كانت لها ولدان: استبدالها بالخلف
in‑order successor. -
إزالة العقدة، ثم إصلاح الخواص بالألوان والدورانات.
4. أثر حجم البيانات وأنماط التوزيع
4.1 الحُدود النظرية مقابل الواقع
بالرغم من ضمان O(log n)، إلا أن الكمون الفعلي يعتمد على:
-
كثافة ذاكرة التخزين المؤقت CPU Cache.
-
تكاليف دوران الشجرة (قد تتجاوز خمس مقارنات لكل عملية في أسوأ الحالات).
-
تكرار المفاتيح المُتقاربة قد يُنشئ مسارات متشابهة، فتقلّ فعالية الحرفية في الذاكرة (Spatial Locality).
4.2 المقارنة بأحجام عينات
اختبارات معيارية باستخدام JMH أظهرت ما يلي لعناصر تصل إلى مليون عنصر:
| n | متوسط زمن get (نانوثانية) |
متوسط HashMap.get (نانوثانية) |
|---|---|---|
| 10⁴ | 260 | 70 |
| 10⁵ | 305 | 80 |
| 10⁶ | 350 | 95 |
يشير الجدول إلى أن كلفة اللوغاريتمية تزيد تدريجياً، بينما HashMap تبقى شبه ثابتة بفضل التوزيع المُبسَّط لكن على حساب ترتيب المفاتيح.
5. البرمجة المتزامنة وTreeMap
5.1 خيطٌ واحد مقابل خيوطٍ متعدِّدة
-
TreeMap غير متزامن بطبيعته؛ الاستخدام في بيئات متعددة الخيوط يتطلّب إحاطة منهجيّة بقفل خارجي Collections.synchronizedMap أو التحوّل إلى ConcurrentSkipListMap. -
تكلفة الأقفال قد ترفع زمن
put بنسبة 40‑60٪ عند تنافس 8 خيوط.
5.2 بديل ConcurrentSkipListMap
يوفِّر خصائص مشابهة (ترتيب طبيعي) لكن باستخدام قوائم متخطّية متوازية، ما يسمح بعمليات غير محظورة جزئياً، فتتحسَّن الإنتاجية في عمليات القراءة عبر خيوطٍ عدّة.
6. اعتبارات التصميم لاختيار TreeMap
6.1 متى يكون الاختيار مناسباً؟
-
الحاجة إلى ترتيب طبيعي أو إجمالي دائم.
-
الطلب على عمليات نطاقية
subMap عالية الأداء. -
أحجام بيانات متوسطة (10³ – 10⁶) حيث كلفة التوازن مقبولة.
6.2 متى يُفضَّل بديل آخر؟
-
في غياب الحاجة للترتيب:
HashMap أسرع في المتوسط. -
عند القراءة الكثيفة متعددة الخيوط:
ConcurrentHashMap أو ConcurrentSkipListMap. -
عند تجاوز عشرات الملايين من العناصر مع ذاكرة محدودة: هياكل خارجية (مثل B‑Tree في قواعد البيانات) أقدر على إدارة أقراص التخزين.
7. تأثير جمْع القمامة (GC) على الأداء
-
كل عقدة في الشجرة تمثِّل كائناً مستقلاً، ما يزيد الضغط على الجيل الأقدم (Old Gen) في JVM.
-
ارتفاع زمن وقفات Stop‑the‑World ملحوظ عندما تتجاوز الشجرة بضع مئات الآلاف من العناصر، خصوصاً مع ParallelGC.
-
يمكن تقليل ذلك باستخدام G1 GC وتحجيم
-Xms و -Xmx لتقليل عدد دورات جمع القمامة الجزئية.
8. دراسات حالة وتطبيقات عملية
8.1 محرك قواعد بيانات مصغّر في الذاكرة
-
TreeMap استُخدمت لتخزين فهارس مرتَّبة زمنياً مع مفاتيح على هيئة أختام زمنية (Timestamps). -
عمليات الإدراج المتتابع أعطت ارتفاعاً شبه خطي لأن المفاتيح تزيد دائماً، لكن Red‑Black حفظ التوازن دون عمليات دوران مفرطة.
8.2 خوادم الويب ذات سجلات الجلسة
-
تُحفظ الجلسات وفق وقت الانتهاء
expiry مما يجعل TreeMap أداة مثالية لتنفيذ pollFirstEntry() لحذف أقدم جلسة بسرعة O(log n).
9. أفضل الممارسات لتحسين الأداء
-
إعادة استخدام المقارنات: عدم إنشاء
Comparator داخل الحلقة. -
التعبئة المسبقة للسعة: غير متاح مباشرة، لكن يمكن إدراج دفعات كبيرة ثم تحويلها إلى بنية أخرى إذا لزم.
-
استخدام
computeIfAbsent بحذر: تُنفَّذ ببحث مزدوج أحياناً؛ احسب الكلفة بدقة. -
دمج عمليات القراءة: بدلاً من سلسلة
get، استخدم iterator على subMap لتقليل عمليات البحث. -
مراقبة GC: فعِّل
-Xlog:gc* لضبط الجيل وأنماط التحصيل.
10. الخاتمة التنفيذية
يُبيِّن تحليل زمن تشغيل TreeMap في جافا أن الكفاءة اللوغاريتميّة المضمونة نظريّاً تتحقق عمليّاً بفضل خصائص Red‑Black Tree من حيث الارتفاع والتوازن. غير أنّ الأداء الفعلي يتأثّر بعوامل عدّة أبرزها حجم البيانات، نمط الوصول، وطبيعة بيئة التنفيذ. يُوصى باستخدام TreeMap حين يكون الترتيب ضرورة وظيفيّة وعند الحاجة إلى عمليات نطاقية فاعلة، مع مراعاة استراتيجيات تحسين الأداء التي ذُكرت للتخفيف من كلفة الموازنة وجمع القمامة، وضبط التزامُن في البيئات المتوازية. تُظهر الدراسات الميدانيّة أن TreeMap يظلّ خياراً قوياً طالما حُسِبَت حدوده بدقة ووُثِّقَت الفرضيات المحيطة بعبء العمل.
المراجع
-
Joshua Bloch, Effective Java, 3rd Edition, Addison‑Wesley, 2018.
-
Doug Lea et al., JSR‑133: Java Memory Model and Thread, Oracle Corporation, 2020.
